LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

  • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:

  1. public class LRUCache {
  3.   int capacity;
  4.   Map<Integer, ListNode> map;
  5.   ListNode head;
  6.   ListNode tail;
  8.   public LRUCache(int cap) {
  9.     capacity = cap;
  10.     map = new HashMap<>();
  11.     head = new ListNode(0, 0);
  12.     tail = new ListNode(0, 0);
  13.     head.next = tail;
  14.     tail.prev = head;
  15.   }
  17.   public int get(int key) {
  18.     if (!map.containsKey(key)) {
  19.       return -1;
  20.     }
  22.     ListNode node = map.get(key);
  23.     promote(node);
  24.     return node.val;
  25.   }
  27.   public void set(int key, int val) {
  28.     ListNode node;
  30.     if (map.containsKey(key)) {
  31.       node = map.get(key);
  32.       promote(node);
  33.       node.val = val;
  34.       return;
  35.     }
  37.     if (map.size() == capacity) {
  38.       ListNode last = tail.prev;
  39.       map.remove(last.key);
  40.       remove(last);
  41.     }
  43.     node = new ListNode(key, val);
  44.     map.put(key, node);
  45.     insert(node);
  46.   }
  48.   void remove(ListNode node) {
  49.     node.prev.next = node.next;
  50.     node.next.prev = node.prev;
  51.   }
  53.   void insert(ListNode node) {
  54.     node.prev = head;
  55.     node.next = head.next;
  56.     head.next.prev = node;
  57.     head.next = node;
  58.   }
  60.   void promote(ListNode node) {
  61.     remove(node);
  62.     insert(node);
  63.   }
  65.   class ListNode {
  66.     int key;
  67.     int val;
  68.     ListNode prev = null;
  69.     ListNode next = null;
  71.     public ListNode(int k, int v) {
  72.       key = k;
  73.       val = v;
  74.     }
  75.   }
  77. }